{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ungraded Lab: Decision Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook you will visualize how a decision tree is splitted using information gain.\n",
    "\n",
    "We will revisit the dataset used in the video lectures. The dataset is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you saw in the lectures, in a decision tree, we decide if a node will be split or not by looking at the **information gain** that split would give us. (Image of video IG)\n",
    "\n",
    "Where \n",
    "\n",
    "$$\\text{Information Gain} = H(p_1^\\text{node})- \\left(w^{\\text{left}}H\\left(p_1^\\text{left}\\right) + w^{\\text{right}}H\\left(p_1^\\text{right}\\right)\\right),$$\n",
    "\n",
    "and $H$ is the entropy, defined as\n",
    "\n",
    "$$H(p_1) = -p_1 \\text{log}_2(p_1) - (1- p_1) \\text{log}_2(1- p_1)$$\n",
    "\n",
    "Remember that log here is defined to be in base 2. Run the code block below to see by yourself how the entropy. $H(p)$ behaves while $p$ varies.\n",
    "\n",
    "Note that the H attains its higher value when $p = 0.5$. This means that the probability of event is $0.5$. And its minimum value is attained in $p = 0$ and $p = 1$, i.e., the probability of the event happening is totally predictable. Thus, the entropy shows the degree of predictability of an event."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from utils import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "2bbd8a6861c2443da67561bc162942ee",
       "version_major": 2,
       "version_minor": 0
      },
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgCAYAAAA10dzkAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8pXeV/AAAACXBIWXMAAA9hAAAPYQGoP6dpAABFX0lEQVR4nO3deXhU5d3G8XuysYRAAgkMOwKCbEWJ7GBUECMqLrW2iLigoqggdW1fpYq7Ql9RaRFXWqu2vopQUXBBBVHW4ApKCDskAyQQCISEJDPvH8dCw5wTJsnkzHK+n+vi6uVzTpJfpvDMPefZXIWFhT4BAADAMWJCXQAAAADsRQAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAR5sILL1RmZqbptb///e9KTk7Wtm3b/K699957Sk5O1qxZs6r9M9966y2lpKTo3XffrfbXAgg/caEuAABQ97Zu3apJkybp5ptv1oQJE6r99aNHj9bmzZs1efJkpaenq0OHDsEvEoBteAIIAA7wyCOPKCUlRQ8++GCNv8c999yj1q1b69FHHw1iZQBCgQAIADXwxBNPKDk5WZ999pkuuugitWzZUp07d9ajjz4qn88X0NfOnTu3Uvtzzz2nZs2a6csvvwxqrVu2bNHcuXP1+9//Xg0bNqzx75GQkKDJkyfr3Xff1ZYtW4JaIwB7EQABoBZuvvlmnXfeeXrllVd0ySWXaPr06Xr11Ver/Jr77rtPQ4cO1eTJk7V9+3ZJ0jfffKNHHnlEU6ZM0dChQ0/6c30+n0pKSvz+lJeX+9374YcfKiEhQZdddlmtf4+LLrpIDRo00MKFC09aI4DwxRxAAKiFlStXqmnTppKkkSNHasuWLfrrX/+qG264wfJrYmJi9NJLL2no0KEaP368/vnPf+qGG27Q8OHDdccddwT8c91ud0D3fvXVVxo4cKCSk5Nr/Xs0atRIgwYN0rJly3TrrbcG9PMBhB+eAAJALTRu3LjSf2dkZGjz5s0qKSmp8uvcbrdeeuklrVq1SkOGDJHP59MLL7wgl8sV0M/t0aOHPvnkE78/d955p9+9Ho9HXbt2Ddrv0blzZ+3evTugOgGEJ54AAkAQNW7cWD6fT/n5+WrTpk2V95599tnKzMzUhx9+qGeffVZNmjQJ+OckJSWpb9++fu0//fSTX9uBAweUlJQU8PeWqv49GjVqpMLCwmp9PwDhhSeAABBEHo9HMTExSklJOem9S5Ys0UcffaROnTrpscceq7Onak2aNFFxcXG1vqaq3+PQoUNVDicDCH8EQAAIkoqKCr333nvq37+/EhMTq7zX4/Hopptu0lVXXaUPPvhAFRUVuummm+T1eoNel9vt1qZNmwK+/2S/R05Ojlq0aBHMEgHYjAAIALXwP//zP3r//ff17rvv6rLLLtOWLVv00EMPVfk1FRUVGjdunBo3bqwnn3xSbrdbM2fO1NKlS/XUU08FvcbBgwfr66+/rvIpYKC/x8GDB/XVV19pyJAhQa8TgH0IgABQC4cOHdLdd9+tW2+9VUeOHNG8efPUv3//Kr/m0Ucf1Zo1a/Tyyy8fe8J2wQUX6KabbtK0adO0ZMmSoNY4cuRIHTp0SPPnz6/17zFv3jyVlJToggsuCGqNAOzlKiwsrHrHUgCAnyeeeEJPPfWU8vPzFRcX/uvpbrjhBv3www9atmyZEhISjrVX5/coLi7WwIED1bdvX7388st1XTKAOsQTQABwgClTpigvL0/Tpk2r8feYOnWqCgoK9MADDwSxMgChQAAEAAfo0KGDnnvuOU2fPl1vvfVWtb9+1qxZmj17tp599ll16NAh+AUCsBVDwAAAAA7DE0AAAACHIQACAAA4DAEQAADAYQiAAAAADkMABAAAcBgCIAAAgMMQAAEAABwm/M8vgiMkJiYqJobPIwCAuuP1enX48OFQlxEWCIAICzExMQRAAABswjsuAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARDVcujQIZ1//vlasGCB5T27d+/WFVdcofT0dA0ZMkRLly61sUIAAHAybAODgL3xxhuaOnWq9u3bV+V9kyZN0ogRIzR+/Hj99NNPuvTSS/Xdd9+pfv36NlUKRL6ScmlvibTniLSvRCoulw6XSYfLpTJv5XvjY6TEOCkxXmoYJzWtLzVvIKXVl+rTywMwQdeAgI0ZM0ZjxozRhRdeaHlPeXm5Pv/8c82ZM0eS1K1bN3Xu3FnLli3T8OHDbaoUCH8+n7T9kLRun/TTfmlLkbS1SNp60GgvKgvOz0mKl9o1kjo0ljokSackSd1SpB5NjXaXKzg/B0BkIQAiqPbu3au4uDg1aNDgWJvb7VZubm4IqwJCy+uTsgul1XukVXuM/123XzoUpJBXlaIy42et2+9/rVG81CNF6ttc6vfLn1OTpRhCIRD1CIAIutjYWL+2o0ePhqASIDS8PumHAunzXdIXudLSPGl/aair8neoTFq5x/jzHyn1pLNaSme3ks5pLfVqRiAEohEBEEGVmpqqsrIyHT58WImJiZIkj8ejVq1ahbgyoG4dKJU+3il9sE36cJsxfy8S7S+V5m81/kjGPMKR7aWL2ksj2kqNE0JZHYBgIQCi1goKClRcXKy2bdsqPj5eQ4cO1RtvvKHx48drw4YN2rBhgwYPHhzqMoGg21civbdF+leO9HmuVO49+ddEmr0l0t82GH/iYqRzWkm/7Sxddoqx2ARAZHIVFhb6Ql0EIsM777yjmTNnKicnR2lpaXK73Vq4cKGeeOIJLVu2TB988IEkKS8vT7fddpu2bdum+vXr6/HHH1dGRkaV3zspKUkxMexKhPB3pFx6b7P0j43SJzuDG/paNjQWanRIklolSmkNjNW8qfWN+XoN44zVvgmx0n9GZX2SjlYYq4OLy41h3fxfVg/vPSLlHv5lcUmRlFccvFrjYqTz2khXnypd1lFqwOMERACv16uioqJQlxEWCIAICwRAhDOfT1qzV3r1J+mtHOlALae0tk6UzkyTejY1VuP2aCp1aVL3W7aUlEvZB4yVx+v2ST/sM36v3MO1+75NEqTRnaVx3Yzfi5XFCFcEwOMIgAgLBECEoyPl0j9zpOd/kL7Jr9n3iHFJfVKNRRWDW0p906TWjYJbZ23tOiSt3it9lWcsWlmbbyxkqYk+qdLtvYxAyB6ECDcEwOMIgAgLBECEk9zDRuh76SepoAaLOdonGYsmzm9rrKhtUi/4NdalwlLpyzzpox3Sgm3Sthq8XzarL93UTZrYyxjOBsIBAfA4AiDCAgEQ4SC7UJr2rfT3DdLRas7t65MqXdFJGtVB6p4SPcOgPp+0fr/0763S/22q/pPQhBjp2q7SPacbewwCoUQAPI4AiLBAAEQo/VggPZwlvbPJWFQRqO4p0lWnSld2ck642Vgovb1JemOjcYJJoFwyAvKf0qWezeqqOqBqBMDjCIAICwRAhEJ2ofTQamOeX6AdYeP/LHg4zThBI1qe9FWXz2ecavLaz8bCmIMBLoxxSfpdZ+nBM6WuKXVaIuCHAHgcARBhgQAIO+Uelh5YZextF+hih9NTpYk9jfDSML5u64s0xWVGCHz+B+m7gsC+JsYlXdNFeqSf1CbMFsUgehEAjyMAIiwQAGGH4jLpz99JT35j7Jl3MjEu6dcdpUm9pMFu5z7tC5TPJ33lkZ77QXp3c2DhukGcdFdv6b4zjL0OgbpEADyOAIiwQABEXfL5jGHe+1ZIOw6d/P6EGOn606S7T5c6N6nz8qJSzgFp+rfGEHEgC2paNJAe62+87pw9jLpCADyOAIiwQABEXVm1W7rjK2nF7pPfWz9Wuq2n8USqJVuXBEXeYeOp619+lEoqTn5//+bSX8+S+qTVfW1wHgLgcQRAhAUCIIKt6Kgxz+/5H06+wCMhRrq5h/THMwh+dSXvsPTEN9LsdSd/IuiSNKGH9Gh/KSXC9lBEeCMAHkcARFggACKYPtgmTVga2HDvfxYitEuq+7pg/H/yp18W4JzszcfdUHrhLOmSU2wpDQ5AADyOAIiwQABEMOwuliZ/Zcz3O5nBbumZwcZWLrDfN3ulu5dLn+06+b2jO0vPDZFSG9R9XYhuBMDjCIAICwRA1Nab2dLty6T9pVXf1z5JenqA9JtOrOoNNZ/POGpu8lfS5oNV39u8gfTXodKvO9lTG6ITAfA4AiDCAgEQNVVYKt261NiHrir1YqUH0qW7e0v14+ypDYE5Ui49/Y0xR7D0JAtFftPJCII8DURNEACPIwAiLBAAURNLc6Wxi6XtJ5nrd3Yr6cUM5xzXFqk2HZBu/1JatKPq+1o2lN4YLp3T2p66ED0IgMfxjgsg4hytkP5nhXT2/KrDX3KC9PLZ0mejCH+RoFMT6cMLpdfOMf6/s5JXLA37tzRllVQewB6DAPzxBBBhgSeACNSmA9LvPpHW7K36vis7Sc8OMVaSIvLkHpZuWSK9v63q+wa7jaeB7VnFjQDwBPA4AiDCAgEQgViwVbp6sXTgqPU9KfWk2RnGXDFENp9PenOjNGmZtK+KxT3JCdIr50iXd7SvNkQmAuBxvOMCCHsVXumBldLFC6sOf+e2lr6/kvAXLVwuaUwXad3vpAvaWd9XeFT69UfSPV8zJAwEiieACAs8AYSV/CPSVZ9Kn+y0vic+Rnq8v3Rnb86RjVZen/TMd9IfV0plVYS889pI/zxPalrfvtoQOXgCeBwBEGGBAAgzq/dIV3xU9UKPbinSm8Ol01Ptqwuhs2aPMQd0UxX7Bp6SJM27QPpVM/vqQmQgAB7HOy6AsPTWRmnovKrD39VdpNW/Jvw5yZnNpbW/ka461fqeLUXSwLnS2wGcCAM4FQEQQFjx+aSH1xjDvlabAsfHSDOHSn8/V0qMt7c+hF7jBOkfw6RXzjY2+DZTXC799hNjuyAv41yAH4aAERYYAoZkBL4bv5D+kW19T+tE6Z0R0gC3bWUhjK3eI122SNp12Pqe33aW5pzDCTBgCPi/8Y4LICzkH5GG/7vq8Hdua2ntFYQ/HNe3uZR1hTSkir8T/8qRRiyQ9pXYVxcQ7giAAEJuw35pwFxpmcf6njt7Sx9dJDVnY2ecoEVDafEo6dYe1vd8mScNek/aUsXiEcBJCIAAQmrVbmnwPOtVnbEu6YWzpD8PkuLosWAhIVb6y1nG0X8JFn9PNhQaHzTW7LGzMiA80Z0CCJnFO6Vz/y0VWAzNNU6QFl4o3VzFkx3gv93QTfr4YuuzhPcckTLmSx+c5Ig5INoRAAGExNzN0sgPpMPl5tc7JEnLL5POa2tvXYh8Ga2kry6T2jUyv15cLl26iG1i4GwEQAC2e/Un6TcfS0ctTnQY0EJaebnUvam9dSF6dG8qrbhcOsNij8hyrzT6U+m1n+2tCwgXBEAAtpr+rXTDF9Z7s13cXvpsFIs9UHstE6Wll1qfI+z1SeM+l2b+YGtZQFggAAKwhc8nPbhKume59T1ju0jvni81YL82BEmjeOnfF0g3drO+Z+Iy6cm19tUEhAMCIABbPLRaejjL+vqkXtKcc6V4i5MdgJqKi5FezJDu7m19zx9XSg+sND6oAE5AAARQ504W/qb2lWYMlmJc9tUEZ3G5pKcHGn/XrDy2VrpvBSEQzkAABFCnpq6Wpq6xvv78EOlPZxpv0EBdcrmMv2vTB1rfM+1b4wMLEO0IgADqzMNrpIcswp9Lxvmst/eytSRAd51ubC5u9Znj4Szp8SqeWAPRgAAIoE48vEZ60OJJikvGfL9rT7O1JOCYm3tIfx9mnDRj5v5V0p+/tbUkwFYEQABB9+dvqw5/r50jXdPVzooAf1d3kd4Ybj339O7lbBGD6EUABBBUr/1svHGacUl69Rye/CF8/Laz8YHEajh44jLpxfW2lgTYggAIIGjmbZFu/ML8mkvSK+dI1xH+EGau6WpsE2PlliXSvzg2DlGGAAggKL7YJf3uE+sTPl4+W7qe8IcwdWN3aeZQ82s+Sdcslj7baWtJQJ0iAAKotay90qiFUmmF+fXnhkjjqjiJAQgHt/WU/jzI/NpRr3TpIunbfHtrAuoKARBArWzYL2UukIrKzK8/eKY0ka1eECHu7C093t/8WlGZdMEH0paD9tYE1AUCIIAa8xRL538g5ZeYX7+tpxEAgUjyxz5GEDTjKZbOXyDtPWJvTUCwEQAB1EhxmTHsu63I/ProzsbQLyd8IBJNGyhddar5tY0HpIs+lA5bPPUGIgEBEEC1eX3S2MXS6j3m1zPbGhs9c7YvIlWMy9ge5rw25tdX7ZGu/Fgq99pbFxAsBEAELCcnR5mZmUpPT9fw4cO1bt060/sWL16sjIwM9evXT4MHD9bChQttrhR17Q8rpLlbzK8NbCG9c76UEGtvTUCwJcRK754v9Uk1v/7hdukeiz0vgXDnKiwstNi0Aahs4MCBevDBB5WZmaklS5bo3nvv1cqVKyvdU1JSolNPPVVffPGFOnXqpPXr12v48OHKyclRw4YNLb93UlKSYmL4PBIJXlwv3bzE/NqpTaTll0vN6ttbE1CXdhdLg9+TNlks/pidIY3vbm9NqBmv16uiIot5Kw7DOy4CsmPHDhUUFCgzM1OSlJGRoeLiYmVnZ1e6r6ysTGVlZcrPN/ZKaNmypeLj4+ViIlhU+HiHdOtS82tN60kfjCT8Ifq0aCh9dJHUvIH59du+lD7fZW9NQG0RABGQ3NxcNW3atFKb2+1WXl5epbakpCTNnj1bF198sUaPHq1rr71WL774oho0sOg5ETF+LJCu+EiqMBkzSIiR5mVKpybbXhZgi05NpPcvkOqbTG0o90q//kjaWGh7WUCNEQARMLMh2tLS0kr/XVxcrJkzZ2ru3Lm6++671a5dO02bNk2HDx+2q0zUgX0lxopfq73+Xj1HGtrK3poAu/VrYSxuMrO/1FgZvL/U/DoQbgiACIjb7T42rPsfHo9HrVpVftf/9NNPlZiYqCFDhig9PV0zZ85UXFycFi9ebGe5CKIKrzT6U2mLxbSZqX2lMV3srQkIld92tt7bMvuAsTK4zOJEHCCcEAARkPbt2yslJUWLFi2SJC1dakwE6969uzwejzwejySpU6dO+v7777Vx40ZJUl5ennbu3KmuXbuGpnDU2v2rjLl/ZsZ2kaak21sPEGp/OlO6spP5tU93SnezMhgRgFXACFh2drYmTpyo/Px8JScna8aMGerVq5cmTJggSZo1a5Yk6e2339YzzzyjiooK1a9fX3fddZcuueSSKr83q4DD09s50m8/Mb82xC19Okqqx3YvcKDiMiljvrRmr/n1N4dLoy02kkbosAr4OAIgwgIBMPz8UCANmCsVl/tfa50oZV1hrI4EnCr3sNTvXWmXyRTnhnHSysulns3srwvWCIDH8Y4LwM/+UumyRebhLyHG2ByX8Aena5Uo/fsCqUGc/7Xicunyj6QDLApBmCIAAqikwitd9Yn1prd/PUvq38LemoBw1SdNejHD/NrGA9J1n0s+xtkQhgiAACp5JEtaZLHoY0IP6YZu9tYDhLuru0i39TS/Nm+L9PS3tpYDBIQACOCYz3ZKD68xvzbYLc0YbG89QKT430HSAIsn4/+zUlq80956gJMhAAKQZJx3OmaxZDZa1SpReud8KYEVv4CphFjp/0ZIaSZHIXp90u8+kXYesr8uwAoBEIC8PmnsYslT7H8tLkZ6Z4TkZtEHUKU2jaR/nifFmBx9nl8iXb3YmGMLhAMCIAA9uVb6xGKI6sn+0kC3vfUAkercNtIT/c2vLcmVHl9rbz2AFQIg4HBf5kpTVptfu6i9dGdve+sBIt09p0uXnWJ+7aE10ld5tpYDmCIAAg6Wf8Q459drMvGvTaJx8L3LZDgLgDWXS3r1HKlDkv81r0+66lNjr00glAiAgEP5fNK1n5mfYhDrkt46T2pmMqEdwMkl1zOOg4s1+QC1/ZB00xfsD4jQIgACDvWXH6UPt5tfe6SfNKSlvfUA0Wag2/i3ZObdzdJLP9lbD/DfCICAA/28X7pnufm189tK951hbz1AtLr3dOnc1ubX7lgmrdtnaznAMQRAwGHKKoztKEoq/K+1bCj9/VzzbSwAVF9sjPT6MCnVZDpFSYWxP2Cpyb9FoK4RAAGHeSRLytprfu3vw6Tm7PcHBFWrXxZUmflxn/SgxSp8oC4RAAEHWeGRHrPYh+yOXtLwNvbWAzjFhe2Nf2Nmpn0rfe2xtRyAAAg4xaEyY+jXbMuXbinSEwPsrwlwkqcGSqen+rd7f1mRf7jM/prgXARAwCHu+lradNC/PS5G+scwqUGc/TUBTlIv1phjm2DyzptzQPrDCvtrgnMRAAEHWLBVenG9+bWpZ0p90mwtB3CsXs2khy22hpn5o7TY4khGINgIgECU218q3bTE/Nogt3QvW74Atrq7tzSghfm1cZ9LBzglBDYgAAJR7q6vJU+xf3tinDEcFUcvANgqNkb627nm0y62H5Lu/Nr+muA8dP1AFPt4h/Taz+bXZgyWOjWxtx4Ahi7J0lMWC69e/dmYtgHUJQIgEKUOlUnjLYZ+M9tKN3Sztx4Ald3WUzqnlfm1m5cyFIy6RQAEotT9K6VtRf7tjeKl2RmSi9M+gJCKcUmvniMlxftfyz0s/XGl/TXBOQiAQBT6Kk96/gfza08NkNol2VsPAHMdGkvPDDa/Nmud8W8ZqAsEQCDKlJRLN34hmez3rLNaSrf0sLsiAFUZd5r1KTzjl3BWMOoGARCIMo9kST8X+rfXj5VeOtsYdgIQPlwu6YWzzFcFr98vPfWN/TUh+hEAgSjybb71m8XUvsbKQwDhp1MT6aEzza89liX9tN/eehD9CIBAlPD6pJuXSBUmY7/padKdve2vCUDgfv8rqXcz//ajXmn8F+bneAM1RQAEosTLP0mr9vi3x8VIr5zNhs9AuIuPlV4+23yaxjKP8W8cCBbeEoAosPeI9UHyfzhD6p1qbz0AaubM5tIdvcyv3bvc2B4GCAYCIBAF/rDCOPP3RJ0aS/f3sb8eADX3cD+pvclWTQeOSvcst78eRCcCIBDhvvYYR0eZeX6IVN9kZSGA8NUoXpo11Pzamxulpbn21oPoRAAEIli5V5qw1PzarztKF7S3tx4AwXFBe2l0Z/Nrt39p/NsHaoMACESwmT9I3xf4tyfGWZ8uACAy/HmQ+TFxP+wzTgkBaoMACESo3MPSn1abX3vwTKltI3vrARBcLROlh/qaX5uyStpdbG89iC4EQCBC3fW1VFTm3949RZr8K/vrARB8E3tK3VL82w8clf640v56ED0IgEAE+mKX9M8c82t/PcvYTwxA5IuPlWYOMb/22s/SCo+99SB6EACBCFPhlX7/tfm1q7tIGa3srQdA3Tq3jXRlJ/Nrty8z+gSgugiAQISZs8E48/dETRKkaQPtrwdA3Zs+SGposqVT1l7pFYttoICqEACBCFJ0VLrfYt7Pg2dK7ob21gPAHm0bSQ+km1/74wppX4m99SDyEQCBCPLEWmn3Ef/2U5tIt/W0vx4A9rmzt9S5iX/7vlLp0Sz760FkIwACEWLrQel/vze/9udBUgILP4CoVi9Wes5if8+ZP0obC20tBxGOAAhEiPtWSKUV/u3D20gXceIH4AgXtDf/917mNfoIIFAEQCACfJUnvb3Jvz3GJf3vIMnlsr8mAKExfaAUZ/Lu/d4WaQnnBCNABEAgzHl91tu+3NRN6tXM3noAhFbXFGlCD/Nrd35l9BnAyRAAgTD3Rra0eo9/e+ME6WGLY6IARLcHz5SSE/zb1+YbfQZwMgRABCwnJ0eZmZlKT0/X8OHDtW6d9Wnkr776qgYNGqQ+ffpo4sSJNlYZXY6UWx/39EAfqTnbvgCO1Ky+NOVM82t/XGn0HUBVTLaVBMyNHTtWDz74oDIzM7VkyRKNGzdOK1f6p5OZM2fqww8/1Lx589S8eXNVVJisXEBAnv9B2nXYv71jY2kS5/0CjnZbT+mvP0qbDlZu33XY6DvuPSM0dSEy8AQQAdmxY4cKCgqUmZkpScrIyFBxcbGysyuPNZSXl2v69Ol64YUX1Lx5c0lSbCz7k9TE/lJj3z8zTw8wtoQA4Fz1YqWnLU7/eWKt0YcAVgiACEhubq6aNm1aqc3tdisvL69S286dO+X1ejVlyhQNHDhQgwcP1pw5c2ysNHo8uVYqPOrfPsgtXd7R/noAhJ/LTjH6hBMVHjX6EMAKQ8AIWEyM/+eF0tLKHzF3796tlJQUTZ8+XWlpadq6dasyMzPVpUsXDRo0yK5SI96OQ9KzP5hfe2oA274AMLhc0pP9pbPm+1977gdpYi+pTSP760L44wkgAuJ2u5Wfn1+pzePxqFWrVpXamjVrJq/Xq7S0NElShw4d1L9/f23cuNG2WqPBQ6vNN32+uL00pKX99QAIX0NbmW8OXVJh9CWAGQIgAtK+fXulpKRo0aJFkqSlS5dKkrp37y6PxyOPxyNJ6tSpkxITEzV37lxJ0p49e7R27Vr1798/NIVHoPX7pDkb/NtjXNLjvIwATDzRXzIbGHhtg9GnACdyFRYWsmUkApKdna2JEycqPz9fycnJmjFjhnr16qUJEyZIkmbNmiVJ2rRpk+68807l5eUpISFB9957r0aNGlXl905KSjIdYnaiyxZJ87b4t1/XVXrtXPvrARAZrvtM+pvJh8fLTpHmZtpfTzjyer0qKioKdRlhgQCIsEAANKzZI/V917+9XqyUPVpql2R/TQAiw/Yiqctb5tNH1lwhpafZX1O4IQAexzsuEEb+ZDFf5/aehD8AVWuXZPQVZv60yt5aEP4IgECY+NojLdzu354UL/2xj/31AIg8fzhDahTv3/7hdmm5x/56EL4IgECYmGLxCX3yr4xjnwDgZFIbGH2GGas+Bs5EAATCwOe7pM92+bcnJ0h39ra/HgCR687eUpME//bFu6QvTPoZOBMBEAgxn8/6k/ndp0vJ9WwtB0CES6ln9B1mpqwy+hyAAAiE2Mc7pK9M5uY0qy9N6mV/PQAi3x29zKeOLPNIn+y0vx6EHwIgEEI+nzR1jfm1P5whJZkM4wDAySQlSPedbn5t6hqeAoIACITUZ7uk5bv9290NpVt72F8PgOhxW0+pRQP/9q89xrxjOBsBEAihhy2e/t13utTQZCsHAAhUw3hjJMHMw1n21oLwQwAEQmRJrrQ0z7+9eQNpfHf76wEQfcZ3N/qUEy3JlZbm2l8PwgcBEAiRRyye/t1zOk//AARHw3jpboutpB7hKaCjEQAd5PDhw9q4caNWr16t7OxsHTp0KNQlOdZyj7En14ma1ZduYe4fgCCa0NN8RfCnO6UVnA7iWHGhLgB1q6KiQm+++abefPNNrVmzRg0aNFBiYqLy8/MlSWeeeaZGjx6tq666SnFx/HWwi9Un77t6mx/jBAA11SheuvNX0v0m+40+kiV9cKH9NSH0eAIYxdauXat+/fpp9uzZGjVqlNauXavt27frp59+0p49e7RmzRqNHDlSzz//vPr166e1a9eGumRHWLPH/MzflHrGqj0ACLbbexknC53ow+1S1l7760HoEQCj2KhRo3TLLbfoyy+/1IQJE9S2bdtj11wul9q3b6+JEydq+fLlGjt2rC666KIQVuscT35j3n5HL6kx+/4BqAONE6Q7LM4IfpLP/o7kKiwsZDvIKPX1119r0KBBAd+/ePFiDRs2rA4rspaUlKSYmOj/PJJdKJ32lnTiP7rGCdLWq42ngABQF/aXSu1fl4rKKre7JG0YLZ2aHIqq7OX1elVUVBTqMsJC9L/jOlh1wp+kkIU/J5n2rX/4k4xNnwl/AOpSSj3pVpNpJj4ZfROchSeADvLdd99pwYIF2r17t1q3bq3rr79ezZs3D3VZkpzxBDD3sHTKP6Sj3srt9WKNp3/uhqGpC4Bz5B2WTnlDKq2o3J4QY/RDLRNDU5ddeAJ4XHS/4+KYv/3tbxo2bJhWrlyp4uJiffTRR+rXr5++/fbbUJfmGDO+9w9/knRdV8IfAHu0TJSu7erfftRr9FFwDp4AOkTv3r01bdo0jRgx4ljb7NmzNW/ePC1cuDCElRmi/QlgYanUzmTuTYzLmHvTuUlo6gLgPDkHpK5vSd4T3v2T4qXtY6XkKJ6OwhPA46L3HReVHDp0SBkZGZXarrnmGv3www8hqshZZq3zD3+SdEVHwh8Ae3VuIv26o397UZn0wjr760FoEAAdYsCAAVqzpvLZY6WlpWrWrFmIKnKOknLroZX7LA5qB4C6ZNX3PPO90Wch+nH0g0PExMTovvvu0wUXXHCsbdu2bWrUqJEee+yxY233339/KMqLav/IlvYc8W8f0Vbqk2Z/PQCQniad10b6ZGfl9j1HpDc2Sjd0C01dsA8B0CH279+v5ORkLV++vFJ7SkrKsTaXyxWK0qKazyf9r9XTv9NtLQUAKrnvDP8AKEn/+5007jSJt4ToRgB0iAULFoS6BEf6aIf0037/9j6p0jmt7a8HAP7j3NbSGanSN/mV29fvlz7eIZ3fLjR1wR7MAQTq0DMWT//u7M2nawCh5XIZfZEZq74L0YMAGMVuvfVWeb0mG89ZuO++++qwGuf5scD4FH2i1onSbzrZXw8AnOjKTlIrk82fP9ph9GGIXgTAKLZu3TqdffbZWrlyZZX3fffddzrvvPNOeh+qx+oT9O09pYRYe2sBADMJsUafZIaNoaMbG0FHsbKyMj399NN64YUX1LZtW40aNUodO3ZUWlqaCgoKtHXrVn3wwQfKycnRzTffrPvuu0/x8fEhqTXaNoLeXWxs/HziyR8N46QdY6Wm9UNTFwCcaF+J1PZ1qfiE7V/qxUrbrpZaRNFJRWwEfRwB0AEKCgo0f/58LV26VNu3b9eBAwfUpEkTtW3bVhkZGbrkkktCvh9gtAXAB1dJD2f5t9/WU5o51P56AKAqty2V/mqyCfSDZ0oP9bW/nrpCADyOAIiwEE0BsKTcePq3t6Ryu0vGsW+nJoeiKgCwll0onfaWdGIgSKsv7bjGeBoYDQiAx7ENTJS7+eabT3rP7NmzbajEOf5vk3/4k6RRHQh/AMJTl2Tp4g7Sv7dWbt9bYvRpV3cJQVGoU9HxyAWWYmNjK/159913/doQXM//aN4++Vf21gEA1WHVRz3PkfFRiSFgh3G73fJ4PKEuw0+0DAGv2i31n+vf3rOp9P2V7P0HIHz5fNKv3pZ+3Od/beXlUr8W9tcUbAwBHxf577ioFo57q1szLZ7+TexF+AMQ3lwu6y1h/mLRtyFyEQCBINlTLP0rx7+9SYI05lT76wGA6hrTxeizTvTPHGnvEfvrQd0hAAJB8tJP/vv+Scah6omh2V4RAKqlUbx0/Wn+7Ue90kvr7a8HdYdVwFHuscceq/TfZWVlfm3333+/nSVFpXKvNMtkDy2XpFsthlQAIBzd2sP8FJBZ66R7z5DieHQUFQiAUW758uWV/nvAgAGV2pgTGBzzt0i7Dvu3X9BO6tzE/noAoKZOTTb6roXbK7fvPGxsE3N5x1BUhWAjAEa5BQsWhLoER7CaIG01oRoAwtntPf0DoGT0dQTA6MCDXKCWsgulz3P92zs1ls5vZ3s5AFBrme2kjo392z/bJW0stL0c1AECIFBLL1pMjJ7QQ4phhB1ABIpxGXMBzVj1eYgsBECgFkorpDkb/NvrxUrXmaykA4BIcW1XKcEkJczZYPR9iGwEQKAW5m6WCkzO/b2io9Ssvv31AECwpDaQrujk355fIr232f56EFwEQKAWZlsMhdzc3d46AKAuWPVlVn0fIgcBEKihn/dLS0wWf3RLkYa0tL8eAAi2oS2l05L927/IlTbst70cBBEBEAHLyclRZmam0tPTNXz4cK1bZ7Lz8X9Zv3692rZtG7Vb0bz0k3n7+G6c+wsgOrhc0niLp4BWfSAiAwEQARs7dqwmT56srKwsTZkyRePGjbO8Nz8/X+PHj1fTpk1trNA+JeXSnJ/92+vFStd0tb8eAKgr13Y1+rYTzdlg9IWITARABGTHjh0qKChQZmamJCkjI0PFxcXKzs72u/fo0aO65pprNHXqVLVp08buUm0xd7O0r9S//cpOUlMWfwCIIk3rS78xWQxSUGL0hYhMBEAEJDc31+9pntvtVl5ent+9kyZN0qhRozRs2DC7yrPdKyZP/yTroRIAiGTju5m3v2rRFyL8EQARsJgY/78upaWVH4PNnj1bDRs21C233GJXWbbbetDYDf9E3VOkwW776wGAujakpbHA7USf7TL6REQeAiAC4na7lZ+fX6nN4/GoVatWldpycnK0ZMkS9e3bV3379tXatWt177336sUXX7Sz3DpltvGzJI07jcUfAKKTy2X0cSfySfqbRZ+I8EYAREDat2+vlJQULVq0SJK0dOlSSVL37t3l8Xjk8XgkSdOmTVNWVpZWr16t1atXq0+fPnr66ac1fvz4kNUeTF6feQCMi5Gu7mJ/PQBgl7FdpFiTD7lzNhh9IyILARABe/311/XMM88oPT1dU6dO1ZtvvqmYmBhNnTpVU6dODXV5tvhil7StyL/9wnZSi4b21wMAdmnRULqwvX/71iLzPVER3lyFhYXkdoRcUlKS6RzDcDN2sfQP/4XPmpcpXXKK/fUAgJ3mbZEuW+TfPraL9PcIWPfn9XpVVGTyKd6Bwv8dFwgTB0qld022PGjeQBrZzv56AMBuF7aT0ky2unpns3TwqP31oOYIgECA3t4kHTHZ9PTqLlK8ySapABBt4mPN5zsfKZfezrG/HtQcARAI0GsW+11dz8kfABzkepPVwJL0GquBIwoBEAjAz/ul5bv9289Mk3o2s78eAAiVXs2k9DT/9q890ob99teDmiEAAgEwW/ghWX8SBoBoZtX3/WOjvXWg5giAwEn4fNIbJp1aQow0+lT76wGAUBvd2egDT/RGttFnIvwRAIGT+Npj7HN1oos7SCn1bC8HAEKuaX3pIpM9AbcUmU+XQfghAAInYfb0T5LG8PQPgIONsTj96A2LKTMILwRAoApHK6R/mWxtkJwgjTT59AsATjGyndEXnuhfm6SyCvvrQfUQAIEqfLRD2lfq3/6bTlI99v4D4GD146QrOvm3F5QYfSfCGwEQqILV6l+zjVABwGms+kJWA4c/AiBg4eBR6d9b/dvbNpKGtLS9HAAIO0NbGn3iieZv4Wi4cEcABCzM3SyVmMxjGXOqFOOyvx4ACDcxLukqkwVxJRXSeyZnpyN8EAABC6z+BYCTs+oTrfpQhAcCIGDCUyx9tsu/vXczjn4DgP/Wq5n0K5N+cfEuoy9FeCIAAibe3Sx5TXaz5+kfAPgz6xu9PmMqDcITARAw8bbJ3n+S9DsCIAD4+V1n8/a3N9lbBwJHAAROkHtY+jLPv32Q23y1GwA4XbskaWAL//aluVLeYfvrwckRAIETvLtZMjvL/EqTDU8BAAazPtIno09F+CEAAif4P4shi193tLcOAIgkZqeCSNZ9KkKLAAj8l12HpGUmw7+D3VIbhn8BwFKbRsZUmRN9mWdMrUF4IQAC/4XhXwCoOYaBIwcBEPgvZivWXGL4FwACcYVFX2m1swJChwAI/GLnIekrj3/7kJZSa4Z/AeCkWjeShpgMAy/zGFNsED4IgMAvrIYoGP4FgMBdabEnIMPA4YUACPyC4V8AqL1fdzT6zhOxKXR4IQACMjYqXW4y/Du0pdQy0f56ACBStUo0ps6c6GsPZwOHEwIgIOn9bearf632tQIAWPuNxWrg97faXQmsEAABSfO2mLdfeoq9dQBANLikg3m7VV8L+xEA4XgHj0qLd/q3p6dx9i8A1ES7JKlPqn/7pzuloqP21wN/BEA43qLt0lGvfztP/wCg5sz60KNeadEO+2uBPwIgHG/+VvP2SzvYWQUARBerD9HzGQYOCwRAONrRCumDbf7tHRtLPZraXw8ARIueTaVTkvzbF2yTyirsrweVEQDhaEtypQMm81EuPUVymW1kBQAIiMtl/hTwwFFpSZ799aAyAiAczXL1bwdbywCAqGQ1DMxq4NAjAMKxvD7z+X+p9aVBJmdZAgCqZ5Db6FNPNG+L5DPbfBW2IQDCsbL2SrsO+7eP6iDF8i8DAGotLka6uIN/+67DRh+M0OFtDo5lNQRhtYEpAKD6rPrU9xgGDikCIBxrgcnq34Zx0nlt7a8FAKLVeW2kBnH+7WY7MMA+BEA40q5D0vcF/u0j2pp3VACAmmkYL41o49/+XYHRFyM0CIBwpIXbzdtHtrO3DgBwgpHtzds5FSR0CIBwJKsAeAEBEACCzqpvteqLUfcIgHCcoxXSJzv923s1ldo0sr8eAIh2bRsZJ4Oc6JOdnAoSKgRAOM7XHqmozL/daogCAFB7ZlNsDh6Vvt5tfy0gAMKBPmT4FwBsZ9XHfshq4JAgAMJxzOacNE6QBrWwvxYAcIrBbikp3r+deYChQQBEwHJycpSZman09HQNHz5c69atM73vxhtvVO/evdW3b19lZmZq/fr1Nldqbcch6cd9/u3ntZHiY+2vBwCcIj7W6GtP9MM+o2+GvQiACNjYsWM1efJkZWVlacqUKRo3bpzpfaNGjVJWVpZWr16tMWPGaNKkSTZXao3tXwAgdCy3g+EpoO0IgAjIjh07VFBQoMzMTElSRkaGiouLlZ2d7XfvqFGjFBdn7KZ8+umny+Px2FprVazmmmQSAAGgzlnOAyQA2o4AiIDk5uaqadPKa/jdbrfy8vKq/Lo5c+ZoxIgRdVlawEorpMW7/NtPT5VaJdpfDwA4TatEqXcz//ZPdxpbdME+HHqFgMXE+H9eKC0ttbz/lVde0YoVK7Rw4cK6LCtgy/KkQ2bbv/D0DwBsM7KdcQzcfztUZvTR55rMEUTd4AkgAuJ2u5Wfn1+pzePxqFWrVqb3P/fcc3r99dc1f/58NW7c2I4ST+ojiyOH2P4FAOxj1eda9dGoGwRABKR9+/ZKSUnRokWLJElLly6VJHXv3l0ej+fYPL+KigrdfffdWrJkid5//32lpqaGrOYTfWYy/NskQRrA9i8AYJuBbqPvPZFZH4264yosLPSFughEhuzsbE2cOFH5+flKTk7WjBkz1KtXL02YMEGSNGvWLG3btk29e/dWx44dFRt7fF+Vv/zlL+rXr5/l905KSjIdYg6W/aVSs1elE/+yX3qK9F5mnf1YAICJSxdK87dWbotxSfnXSyn16u7ner1eFRUV1d0PiCAEQISFug6A722WLv/Iv/25IdLEXnX2YwEAJp77XrrjK//29zKND+Z1hQB4HEPAcASroYVhre2tAwAgDbNY7MEwsH0IgHAEs+1f3A2lbin21wIATtc9RWrRwL998U77a3EqAiCiXt5h6af9/u3ntpZcLvvrAQCnc7mMPvhE6/dLnmL763EiAiCintWQglnnAwCwh1Uf/BlPAW1BAETUY/4fAIQf5gGGFgEQUc3nM5//d0qS1CE89qcGAEc6pbHUIcm/3azPRvARABHVthRJ20xW/Ft98gQA2MdsJGZrkbTloP21OA0BEFHNakUZ8/8AIPSs+mJWA9c9AiCiGgtAACB8ncs8wJAhACJq+XzmnUiPFKlFQ/vrAQBU5m5o7Al4os92GX046g4BEFFr3T5pzxH/dub/AUD4MOuTdx8x+nDUHQIgotbSPPN2hn8BIHxY9clfWvThCA4CIKKWWefhknRWK9tLAQBYOKuleTsBsG4RABGVfD7zzqNnUymlnv31AADMNa1v9M0nWuaxvxYnIQAiKm0rknYd9m8fYvFJEwAQOkPc/m07Dpnv44rgIAAiKlkNHQwlAAJA2LHqmxkGrjsEQEQlq6EDngACQPix6puXEQDrDAEQUcnsU2P7JKltI/trAQBUrV2S1M6kf+YJYN0hACLq5B+Rftrv387wLwCEL7M+ev1+qaDE/lqcgACIqLNyj3m72SRjAEB4sBoGXrnb3jqcggCIqLPCorMYRAAEgLBl1Udb9emoHQIgoo5ZZ9Eo3vy8SQBAeOiRIiXG+bcTAOsGARBRxeuTVpkMAfdrLsXytx0AwlZsjNFXn2jlHqNvR3Dxloio8vN+6eBR//YBLeyvBQBQPWZ99cGj0oZC20uJegRARBWroYL+Jp8qAQDhpb/Fh3WGgYOPAIioYhkAeQIIAGGPAGgfAiCiilkncUqS1KKh/bUAAKrH3VDqkOTfTgAMPgIgosahMmmdyQbQzP8DgMhh1mf/uM/o4xE8BEBEje/yzVeKma0qAwCEJ7M5216f9H2B/bVEMwIgosbafPP2MwmAABAx0tPM29futbeOaEcARNQw6xxckno3s70UAEANnZ5q3m71IR81QwBE1PjGpHM4tYmUlGB/LQCAmklKMPruE5n18ag5AiCiQkm5+QKQPhZDCQCA8GXWd/+4TyqtsL+WaEUARFT4cZ9U7vVv72MxlAAACF9mfXe51+jrERwEQEQFq7khZ/AEEAAizhlW8wBZCBI0BEBEhW8sOgWrTgQAEL6s+m7mAQYPARBRwewJYPskqVl9+2sBANROagOpXSP/dp4ABg8BEBHP65N+MJkXwtM/AIhcZn349/vMN/xH9REAEfF2HJKOlPu3/6qp/bUAAILDbA/XI+XSzkP21xKNCICIeBsKzdtPS7G1DABAEHVNNm+36vNRPQRARDyrzsCq8wAAhL+uFh/iCYDBQQBExLPqDMx2kgcARAarPpwAGBwEQES87EL/tlaJHAEHAJGscYLUsqF/e/YB+2uJRgRARDyzT4NdefoHABHPbCoPTwCDIy7UBQC1UXzUp86rF+vPX76gZofzVZCYqllDb1GXbsMkuUJdHgCgFromS1/kVm7bXmSsBm5AgqkVXj5EruXLFXv1tXonb69SjhQeax62YbE0P03619+lAQNCVx8AoFbMngD6JG08IP3KZJsYBI4hYAQsJydHmZmZSk9P1/Dhw7Vu3bpa3Vcry5dLl1+ueps3Vgp/kpRypFAp2zdKl14qrVgR/J8NALBFl2TzdrO536geAiACNnbsWE2ePFlZWVmaMmWKxo0bV6v7asznk669VvJ4qr5v927pmmuM+wEAEYe9AOsOARAB2bFjhwoKCpSZmSlJysjIUHFxsbKzs2t0X60sXiztDfBAyL17pc8+C97PBgDYpkOSFG+SVAiAtUcAREByc3PVtGnls9Xcbrfy8vJqdF+tvPCCVFgY2L2FhdKsWcH72QAA28TFSJ1NdnXYV2p/LdGGRSAIWEyM/+eF0lL/f4WB3ldj+fnVu7+gIHg/GwBgqxu7SUVHjeHgrsnSqclSo/gQFxUFCIAIiNvtVv4Jwcvj8ahVq1Y1uq9WUlOrd38zlooBQKS6s3eoK4hODAEjIO3bt1dKSooWLVokSVq6dKkkqXv37vJ4PPL8siCjqvuC5pZbpOTkwO5NTpYmTAjezwYAIAq4CgsLWSKJgGRnZ2vixInKz89XcnKyZsyYoV69emnCLwFr1i9z7azuq0pSUpLp0LEpn0/q2lXauPHk9556qrRhg+RiU2gAcDqv16uioqJQlxEWCIAIC9UKgJKxD+BllxlbvVhp0UKaP1/q37/2BQIAIh4B8DiGgBGZBg6U5s0znvCdOBycnGy0E/4AADDFE0CEhWo/AfwPn8/Y52/WLGO1b7Nmxpy/c89l2BcAUAlPAI8jACIs1DgAAgAQIALgcbzjAgAAOAwBEAAAwGEIgAAAAA7DSSAIC16vN9QlAACiHO81xxEAERYOHz4c6hIAAHAMhoABAAAchgAIAADgMARAAAAAhyEAAgAAOAwBEAAAwGEIgAAAAA5DAEREycnJUWZmptLT0zV8+HCtW7euVvdFs0BfgxtvvFG9e/dW3759lZmZqfXr19tcaXio7t+Z9evXq23btlqwYIFNFYaX6rxer776qgYNGqQ+ffpo4sSJNlYZHgJ9rRYvXqyMjAz169dPgwcP1sKFC22uNHwcOnRI559/fpX/vnbv3q0rrrhC6enpGjJkiJYuXWpjhZGPAIiIMnbsWE2ePFlZWVmaMmWKxo0bV6v7olmgr8GoUaOUlZWl1atXa8yYMZo0aZLNlYaH6vydyc/P1/jx49W0aVMbKwwvgb5eM2fO1DvvvKN58+Zp7dq1mjFjhr2FhoFAXquSkhJdd911evXVV7Vq1Sq99NJLuuGGG1RcXByCikPrjTfeUJ8+fZSVlVXlfZMmTdKIESOUlZWll156STfddJNKSkpsqjLyEQARMXbs2KGCggJlZmZKkjIyMlRcXKzs7Owa3RfNqvMajBo1SnFxxp7wp59+ujwej621hoPqvF5Hjx7VNddco6lTp6pNmzZ2lxoWAn29ysvLNX36dL3wwgtq3ry5JCk2Ntb2ekMp0NeqrKxMZWVlys/PlyS1bNlS8fHxcrlcttccamPGjFF2drb69+9veU95ebk+//xzjR07VpLUrVs3de7cWcuWLbOrzIhHAETEyM3N9Xvi4na7lZeXV6P7ollNX4M5c+ZoxIgRdVlaWKrO6zVp0iSNGjVKw4YNs6u8sBPo67Vz5055vV5NmTJFAwcO1ODBgzVnzhwbKw29QF+rpKQkzZ49WxdffLFGjx6ta6+9Vi+++KIaNGhgZ7kRY+/evYqLi6v0+rjdbuXm5oawqsjCUXCIKDEx/p9ZSktLa3xfNKvua/DKK69oxYoVjp13FMjrNXv2bDVs2FC33HKLXWWFrUBer927dyslJUXTp09XWlqatm7dqszMTHXp0kWDBg2yq9SQC+S1Ki4u1syZMzV37lw1aNBAr732mqZNm6YhQ4YoMTHRrlIjitnT5KNHj4agksjEE0BEDLfbfWx45D88Ho9atWpVo/uiWXVfg+eee06vv/665s+fr8aNG9tRYlgJ9PXKycnRkiVL1LdvX/Xt21dr167VvffeqxdffNHOckMu0NerWbNm8nq9SktLkyR16NBB/fv318aNG22rNdQCfa0+/fRTJSYmasiQIUpPT9fMmTMVFxenxYsX21luxEhNTVVZWVmlc+Sd1s/XFgEQEaN9+/ZKSUnRokWLJOnYiq/u3bvL4/Ecm7tW1X1OEehrVVFRobvvvltLlizR+++/r9TU1JDVHEqBvl7Tpk07tmBm9erV6tOnj55++mmNHz8+ZLWHQqCvV6dOnZSYmKi5c+dKkvbs2aO1a9dWObcr2lTntfr++++PheO8vDzt3LlTXbt2DU3hYaigoEA7duyQJMXHx2vo0KF64403JEkbNmzQhg0bNHjw4FCWGFFchYWFvlAXAQQqOztbEydOVH5+vpKTkzVjxgz16tVLEyZMkCTNmjWryvucJJDXatu2berdu7c6duxYaTjlL3/5i/r16xeq0kMi0L9b/+3CCy/UhAkTdNFFF9ldbsgF+npt2rRJd955p/Ly8pSQkKB7771Xo0aNCmXptgv0tXr77bf1zDPPqKKiQvXr19ddd92lSy65JJSlh8Q777yjmTNnKicnR2lpaXK73Vq4cKGeeOIJLVu2TB988IEkIyTfdttt2rZtm+rXr6/HH39cGRkZIa4+chAAAQAAHIYhYAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIeJC3UBAIDAXXjhhUpJSZHX69WKFSuUmJiou+66S9ddd12oSwMQQXgCCAARZvPmzbrlllu0bt06TZ8+XXfddZe+/fbbUJcFIIIQAAEgwowcOVJnnXWWGjRooPPPP1+DBg3SggULQl0WgAhCAASACNe8eXN5PJ5QlwEgghAAASDCbd68Wa1btw51GQAiCItAACDCbN26VYWFhUpISNDrr7+uTZs26frrrw91WQAiCAEQACLM+vXrddZZZyk/P1+9evXSvHnz5Ha7Q10WgAhCAASACDNy5Eg98MADoS4DQARjDiAAAIDDEAABAAAcxlVYWOgLdREAAACwD08AAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwmLhQFwBn8vl8qqioUEVFhWJjYxUbGyuXyxXqsgAAcAQCIGxVXl6uffv2KT8/X6Wlpcfa69Wrp9TUVDVt2lRxcfy1BACgLrkKCwt9oS4CznDw4EFt3bpVXq9XqampSktLU1xcnMrLy7V3717l5+crJiZGHTp0UOPGjUNdLgAAUYsACFscPHhQmzdvVkpKirp27ap69er53VNaWqoNGzZo//796tixIyEQAIA6QgBEnSsvL9f69evVpEkT9ezZUzEx1muPvF6vfvzxR+3fv18pKSlV3gsAQE21bds2oPtycnJ0++23a+/evUpJSdGzzz6rHj161HF1dY93VwRFcnKyfv/732vo0KHq1auXXnnllWPX9u3bJ6/Xq65du5400MXExKhr167y+XyV5ggCABAKY8eO1eTJk5WVlaUpU6Zo3LhxoS4pKAiACJrMzEx9+eWX+vjjj/Xoo49qx44d8vl8ys/PV2pqqumwr5l69eopLS1NJSUl8vl4QA0ACI0dO3aooKBAmZmZkqSMjAwVFxcrOzs7xJXVHgEQQdO/f39JUsuWLZWenq7vvvtOFRUVKi0tVVpaWrW+V1pamioqKgiAAICQyc3NVdOmTSu1ud1u5eXlhaii4CEAok6Ulpaqfv36qqiokKRqb+3yn/sJgACAUDKbuhQNU5QIgAiaI0eOSJK+//575eTkqG/fvoqNjZVkLASpjv/cz+bQAIBQcbvdys/Pr9Tm8XjUqlWrEFUUPOy4i6C5/vrrtW/fPtWrV08vv/yymjRpIp/Pp3r16mnv3r1q3rx5wN9r7969nA4CAAip9u3bKyUlRYsWLVJmZqaWLl0qSerevXuIK6s9toFBUCQnJ2vr1q1KTk72u7Znzx7l5uZqwIABAS0EKS0t1YoVK9SqVatqhUYAAIItOztbEydOVH5+vpKTkzVjxgz16tUr1GXVGgEQQVFVAKzJPoAHDhxQ9+7dORYOAIA6QACELTgJBACA8EEAhG04CxgAgPBAAIStysvLtW/fPuXn51daRl+vXj2lpqaqWbNmx1YOAwCAukEAREj4fD5VVFSooqJCsbGxrPgFAMBGzLBHSLhcLsXFxbHIAwCAEGAjaAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwGAIgAACAwxAAAQAAHIYACAAA4DAEQAAAAIchAAIAADgMARAAAMBhCIAAAAAOQwAEAABwmP8HAq7ZRVAhC8AAAAAASUVORK5CYII=",
      "text/html": [
       "\n",
       "            <div style=\"display: inline-block;\">\n",
       "                <div class=\"jupyter-widgets widget-label\" style=\"text-align: center;\">\n",
       "                    Figure\n",
       "                </div>\n",
       "                <img src='' width=640.0/>\n",
       "            </div>\n",
       "        "
      ],
      "text/plain": [
       "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib widget\n",
    "_ = plot_entropy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|                                                     |   Ear Shape | Face Shape | Whiskers |   Cat  |\n",
    "|:---------------------------------------------------:|:---------:|:-----------:|:---------:|:------:|\n",
    "| <img src=\"images/0.png\" alt=\"drawing\" width=\"50\"/> |   Pointy   |   Round     |  Present  |    1   |\n",
    "| <img src=\"images/1.png\" alt=\"drawing\" width=\"50\"/> |   Floppy   |  Not Round  |  Present  |    1   |\n",
    "| <img src=\"images/2.png\" alt=\"drawing\" width=\"50\"/> |   Floppy   |  Round      |  Absent   |    0   |\n",
    "| <img src=\"images/3.png\" alt=\"drawing\" width=\"50\"/> |   Pointy   |  Not Round  |  Present  |    0   |\n",
    "| <img src=\"images/4.png\" alt=\"drawing\" width=\"50\"/> |   Pointy   |   Round     |  Present  |    1   |\n",
    "| <img src=\"images/5.png\" alt=\"drawing\" width=\"50\"/> |   Pointy   |   Round     |  Absent   |    1   |\n",
    "| <img src=\"images/6.png\" alt=\"drawing\" width=\"50\"/> |   Floppy   |  Not Round  |  Absent   |    0   |\n",
    "| <img src=\"images/7.png\" alt=\"drawing\" width=\"50\"/> |   Pointy   |  Round      |  Absent   |    1   |\n",
    "| <img src=\"images/8.png\" alt=\"drawing\" width=\"50\"/> |    Floppy  |   Round     |  Absent   |    0   |\n",
    "| <img src=\"images/9.png\" alt=\"drawing\" width=\"50\"/> |   Floppy   |  Round      |  Absent   |    0   |\n",
    "\n",
    "\n",
    "We will use **one-hot encoding** to encode the categorical features. They will be as follows:\n",
    "\n",
    "- Ear Shape: Pointy = 1, Floppy = 0\n",
    "- Face Shape: Round = 1, Not Round = 0\n",
    "- Whiskers: Present = 1, Absent = 0\n",
    "\n",
    "Therefore, we have two sets:\n",
    "\n",
    "- `X_train`: for each example, contains 3 features:\n",
    "            - Ear Shape (1 if pointy, 0 otherwise)\n",
    "            - Face Shape (1 if round, 0 otherwise)\n",
    "            - Whiskers (1 if present, 0 otherwise)\n",
    "            \n",
    "- `y_train`: whether the animal is a cat\n",
    "            - 1 if the animal is a cat\n",
    "            - 0 otherwise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train = np.array([[1, 1, 1],\n",
    "[0, 0, 1],\n",
    " [0, 1, 0],\n",
    " [1, 0, 1],\n",
    " [1, 1, 1],\n",
    " [1, 1, 0],\n",
    " [0, 0, 0],\n",
    " [1, 1, 0],\n",
    " [0, 1, 0],\n",
    " [0, 1, 0]])\n",
    "\n",
    "y_train = np.array([1, 1, 0, 0, 1, 1, 0, 1, 0, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 1, 1])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#For instance, the first example\n",
    "X_train[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This means that the first example has a pointy ear shape, round face shape and it has whiskers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On each node, we compute the information gain for each feature, then split the node on the feature with the higher information gain, by comparing the entropy of the node with the weighted entropy in the two splitted nodes. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, the root node has every animal in our dataset. Remember that $p_1^{node}$ is the proportion of positive class (cats) in the root node. So\n",
    "\n",
    "$$p_1^{node} = \\frac{5}{10} = 0.5$$\n",
    "\n",
    "Now let's write a function to compute the entropy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n"
     ]
    }
   ],
   "source": [
    "def entropy(p):\n",
    "    if p == 0 or p == 1:\n",
    "        return 0\n",
    "    else:\n",
    "        return -p * np.log2(p) - (1 - p) * np.log2(1 - p)\n",
    "    \n",
    "print(entropy(0.5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To illustrate, let's compute the information gain if we split the node for each of the features. To do this, let's write some functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_indices(X, index_feature):\n",
    "    \"\"\"Given a dataset and a index feature, return two lists for the two split nodes, the left node has the animals that have \n",
    "    that feature = 1 and the right node those that have the feature = 0 \n",
    "    index feature = 0 => ear shape\n",
    "    index feature = 1 => face shape\n",
    "    index feature = 2 => whiskers\n",
    "    \"\"\"\n",
    "    left_indices = []\n",
    "    right_indices = []\n",
    "    for i, x in enumerate(X):\n",
    "        if x[index_feature] == 1:\n",
    "            left_indices.append(i)\n",
    "        else:\n",
    "            right_indices.append(i)\n",
    "    return left_indices, right_indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, if we choose Ear Shape to split, then we must have in the left node (check the table above) the indices:\n",
    "\n",
    "$$0 \\quad 3 \\quad 4 \\quad 5 \\quad 7$$\n",
    "\n",
    "and the right indices, the remaining ones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0, 3, 4, 5, 7], [1, 2, 6, 8, 9])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "split_indices(X_train, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need another function to compute the weighted entropy in the splitted nodes. As you've seen in the video lecture, we must find:\n",
    "\n",
    "- $w^{\\text{left}}$ and $w^{\\text{right}}$, the proportion of animals in **each node**.\n",
    "- $p^{\\text{left}}$ and $p^{\\text{right}}$, the proportion of cats in **each split**.\n",
    "\n",
    "Note the difference between these two definitions!! To illustrate, if we split the root node on the feature of index 0 (Ear Shape), then in the left node, the one that has the animals 0, 3, 4, 5 and 7, we have:\n",
    "\n",
    "$$w^{\\text{left}}= \\frac{5}{10} = 0.5 \\text{ and } p^{\\text{left}} = \\frac{4}{5}$$\n",
    "$$w^{\\text{right}}= \\frac{5}{10} = 0.5 \\text{ and } p^{\\text{right}} = \\frac{1}{5}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def weighted_entropy(X,y,left_indices,right_indices):\n",
    "    \"\"\"\n",
    "    This function takes the splitted dataset, the indices we chose to split and returns the weighted entropy.\n",
    "    \"\"\"\n",
    "    w_left = len(left_indices)/len(X)\n",
    "    w_right = len(right_indices)/len(X)\n",
    "    p_left = sum(y[left_indices])/len(left_indices)\n",
    "    p_right = sum(y[right_indices])/len(right_indices)\n",
    "    \n",
    "    weighted_entropy = w_left * entropy(p_left) + w_right * entropy(p_right)\n",
    "    return weighted_entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7219280948873623"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "left_indices, right_indices = split_indices(X_train, 0)\n",
    "weighted_entropy(X_train, y_train, left_indices, right_indices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, the weighted entropy in the 2 split nodes is 0.72. To compute the **Information Gain** we must subtract it from the entropy in the node we chose to split (in this case, the root node). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def information_gain(X, y, left_indices, right_indices):\n",
    "    \"\"\"\n",
    "    Here, X has the elements in the node and y is theirs respectives classes\n",
    "    \"\"\"\n",
    "    p_node = sum(y)/len(y)\n",
    "    h_node = entropy(p_node)\n",
    "    w_entropy = weighted_entropy(X,y,left_indices,right_indices)\n",
    "    return h_node - w_entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.2780719051126377"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "information_gain(X_train, y_train, left_indices, right_indices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's compute the information gain if we split the root node for each feature:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Feature: Ear Shape, information gain if we split the root node using this feature: 0.28\n",
      "Feature: Face Shape, information gain if we split the root node using this feature: 0.03\n",
      "Feature: Whiskers, information gain if we split the root node using this feature: 0.12\n"
     ]
    }
   ],
   "source": [
    "for i, feature_name in enumerate(['Ear Shape', 'Face Shape', 'Whiskers']):\n",
    "    left_indices, right_indices = split_indices(X_train, i)\n",
    "    i_gain = information_gain(X_train, y_train, left_indices, right_indices)\n",
    "    print(f\"Feature: {feature_name}, information gain if we split the root node using this feature: {i_gain:.2f}\")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, the best feature to split is indeed the Ear Shape. Run the code below to see the split in action. You do not need to understand the following code block. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Depth 0, Root: Split on feature: 0\n",
      " - Left leaf node with indices [0, 3, 4, 5, 7]\n",
      " - Right leaf node with indices [1, 2, 6, 8, 9]\n"
     ]
    },
    {
     "ename": "FileNotFoundError",
     "evalue": "[WinError 2] \"dot\" not found in path.",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mFileNotFoundError\u001b[0m                         Traceback (most recent call last)",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\pydot.py:1923\u001b[0m, in \u001b[0;36mDot.create\u001b[1;34m(self, prog, format, encoding)\u001b[0m\n\u001b[0;32m   1922\u001b[0m \u001b[39mtry\u001b[39;00m:\n\u001b[1;32m-> 1923\u001b[0m     stdout_data, stderr_data, process \u001b[39m=\u001b[39m call_graphviz(\n\u001b[0;32m   1924\u001b[0m         program\u001b[39m=\u001b[39;49mprog,\n\u001b[0;32m   1925\u001b[0m         arguments\u001b[39m=\u001b[39;49marguments,\n\u001b[0;32m   1926\u001b[0m         working_dir\u001b[39m=\u001b[39;49mtmp_dir,\n\u001b[0;32m   1927\u001b[0m     )\n\u001b[0;32m   1928\u001b[0m \u001b[39mexcept\u001b[39;00m \u001b[39mOSError\u001b[39;00m \u001b[39mas\u001b[39;00m e:\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\pydot.py:132\u001b[0m, in \u001b[0;36mcall_graphviz\u001b[1;34m(program, arguments, working_dir, **kwargs)\u001b[0m\n\u001b[0;32m    130\u001b[0m program_with_args \u001b[39m=\u001b[39m [program, ] \u001b[39m+\u001b[39m arguments\n\u001b[1;32m--> 132\u001b[0m process \u001b[39m=\u001b[39m subprocess\u001b[39m.\u001b[39mPopen(\n\u001b[0;32m    133\u001b[0m     program_with_args,\n\u001b[0;32m    134\u001b[0m     env\u001b[39m=\u001b[39menv,\n\u001b[0;32m    135\u001b[0m     cwd\u001b[39m=\u001b[39mworking_dir,\n\u001b[0;32m    136\u001b[0m     shell\u001b[39m=\u001b[39m\u001b[39mFalse\u001b[39;00m,\n\u001b[0;32m    137\u001b[0m     stderr\u001b[39m=\u001b[39msubprocess\u001b[39m.\u001b[39mPIPE,\n\u001b[0;32m    138\u001b[0m     stdout\u001b[39m=\u001b[39msubprocess\u001b[39m.\u001b[39mPIPE,\n\u001b[0;32m    139\u001b[0m     \u001b[39m*\u001b[39m\u001b[39m*\u001b[39mkwargs\n\u001b[0;32m    140\u001b[0m )\n\u001b[0;32m    141\u001b[0m stdout_data, stderr_data \u001b[39m=\u001b[39m process\u001b[39m.\u001b[39mcommunicate()\n",
      "File \u001b[1;32m~\\AppData\\Local\\Programs\\Python\\Python310\\lib\\subprocess.py:971\u001b[0m, in \u001b[0;36mPopen.__init__\u001b[1;34m(self, args, bufsize, executable, stdin, stdout, stderr, preexec_fn, close_fds, shell, cwd, env, universal_newlines, startupinfo, creationflags, restore_signals, start_new_session, pass_fds, user, group, extra_groups, encoding, errors, text, umask, pipesize)\u001b[0m\n\u001b[0;32m    968\u001b[0m             \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mstderr \u001b[39m=\u001b[39m io\u001b[39m.\u001b[39mTextIOWrapper(\u001b[39mself\u001b[39m\u001b[39m.\u001b[39mstderr,\n\u001b[0;32m    969\u001b[0m                     encoding\u001b[39m=\u001b[39mencoding, errors\u001b[39m=\u001b[39merrors)\n\u001b[1;32m--> 971\u001b[0m     \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49m_execute_child(args, executable, preexec_fn, close_fds,\n\u001b[0;32m    972\u001b[0m                         pass_fds, cwd, env,\n\u001b[0;32m    973\u001b[0m                         startupinfo, creationflags, shell,\n\u001b[0;32m    974\u001b[0m                         p2cread, p2cwrite,\n\u001b[0;32m    975\u001b[0m                         c2pread, c2pwrite,\n\u001b[0;32m    976\u001b[0m                         errread, errwrite,\n\u001b[0;32m    977\u001b[0m                         restore_signals,\n\u001b[0;32m    978\u001b[0m                         gid, gids, uid, umask,\n\u001b[0;32m    979\u001b[0m                         start_new_session)\n\u001b[0;32m    980\u001b[0m \u001b[39mexcept\u001b[39;00m:\n\u001b[0;32m    981\u001b[0m     \u001b[39m# Cleanup if the child failed starting.\u001b[39;00m\n",
      "File \u001b[1;32m~\\AppData\\Local\\Programs\\Python\\Python310\\lib\\subprocess.py:1440\u001b[0m, in \u001b[0;36mPopen._execute_child\u001b[1;34m(self, args, executable, preexec_fn, close_fds, pass_fds, cwd, env, startupinfo, creationflags, shell, p2cread, p2cwrite, c2pread, c2pwrite, errread, errwrite, unused_restore_signals, unused_gid, unused_gids, unused_uid, unused_umask, unused_start_new_session)\u001b[0m\n\u001b[0;32m   1439\u001b[0m \u001b[39mtry\u001b[39;00m:\n\u001b[1;32m-> 1440\u001b[0m     hp, ht, pid, tid \u001b[39m=\u001b[39m _winapi\u001b[39m.\u001b[39;49mCreateProcess(executable, args,\n\u001b[0;32m   1441\u001b[0m                              \u001b[39m# no special security\u001b[39;49;00m\n\u001b[0;32m   1442\u001b[0m                              \u001b[39mNone\u001b[39;49;00m, \u001b[39mNone\u001b[39;49;00m,\n\u001b[0;32m   1443\u001b[0m                              \u001b[39mint\u001b[39;49m(\u001b[39mnot\u001b[39;49;00m close_fds),\n\u001b[0;32m   1444\u001b[0m                              creationflags,\n\u001b[0;32m   1445\u001b[0m                              env,\n\u001b[0;32m   1446\u001b[0m                              cwd,\n\u001b[0;32m   1447\u001b[0m                              startupinfo)\n\u001b[0;32m   1448\u001b[0m \u001b[39mfinally\u001b[39;00m:\n\u001b[0;32m   1449\u001b[0m     \u001b[39m# Child is launched. Close the parent's copy of those pipe\u001b[39;00m\n\u001b[0;32m   1450\u001b[0m     \u001b[39m# handles that only the child should have open.  You need\u001b[39;00m\n\u001b[1;32m   (...)\u001b[0m\n\u001b[0;32m   1453\u001b[0m     \u001b[39m# pipe will not close when the child process exits and the\u001b[39;00m\n\u001b[0;32m   1454\u001b[0m     \u001b[39m# ReadFile will hang.\u001b[39;00m\n",
      "\u001b[1;31mFileNotFoundError\u001b[0m: [WinError 2] The system cannot find the file specified",
      "\nDuring handling of the above exception, another exception occurred:\n",
      "\u001b[1;31mFileNotFoundError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\C2 - Advanced Learning Algorithms\\week4\\optional labs\\C2_W4_Lab_01_Decision_Trees.ipynb Cell 26\u001b[0m line \u001b[0;36m4\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/TA/machine-learning-specialization-coursera/C2%20-%20Advanced%20Learning%20Algorithms/week4/optional%20labs/C2_W4_Lab_01_Decision_Trees.ipynb#X36sZmlsZQ%3D%3D?line=0'>1</a>\u001b[0m tree \u001b[39m=\u001b[39m []\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/TA/machine-learning-specialization-coursera/C2%20-%20Advanced%20Learning%20Algorithms/week4/optional%20labs/C2_W4_Lab_01_Decision_Trees.ipynb#X36sZmlsZQ%3D%3D?line=1'>2</a>\u001b[0m build_tree_recursive(X_train, y_train, [\u001b[39m0\u001b[39m,\u001b[39m1\u001b[39m,\u001b[39m2\u001b[39m,\u001b[39m3\u001b[39m,\u001b[39m4\u001b[39m,\u001b[39m5\u001b[39m,\u001b[39m6\u001b[39m,\u001b[39m7\u001b[39m,\u001b[39m8\u001b[39m,\u001b[39m9\u001b[39m], \u001b[39m\"\u001b[39m\u001b[39mRoot\u001b[39m\u001b[39m\"\u001b[39m, max_depth\u001b[39m=\u001b[39m\u001b[39m1\u001b[39m, current_depth\u001b[39m=\u001b[39m\u001b[39m0\u001b[39m, tree \u001b[39m=\u001b[39m tree)\n\u001b[1;32m----> <a href='vscode-notebook-cell:/d%3A/TA/machine-learning-specialization-coursera/C2%20-%20Advanced%20Learning%20Algorithms/week4/optional%20labs/C2_W4_Lab_01_Decision_Trees.ipynb#X36sZmlsZQ%3D%3D?line=3'>4</a>\u001b[0m generate_tree_viz([\u001b[39m0\u001b[39;49m,\u001b[39m1\u001b[39;49m,\u001b[39m2\u001b[39;49m,\u001b[39m3\u001b[39;49m,\u001b[39m4\u001b[39;49m,\u001b[39m5\u001b[39;49m,\u001b[39m6\u001b[39;49m,\u001b[39m7\u001b[39;49m,\u001b[39m8\u001b[39;49m,\u001b[39m9\u001b[39;49m], y_train, tree)\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\C2 - Advanced Learning Algorithms\\week4\\optional labs\\utils.py:185\u001b[0m, in \u001b[0;36mgenerate_tree_viz\u001b[1;34m(root_indices, y, tree)\u001b[0m\n\u001b[0;32m    181\u001b[0m     root \u001b[39m+\u001b[39m\u001b[39m=\u001b[39m \u001b[39m1\u001b[39m\n\u001b[0;32m    184\u001b[0m node_names \u001b[39m=\u001b[39m decision_names \u001b[39m+\u001b[39m leaf_names\n\u001b[1;32m--> 185\u001b[0m pos \u001b[39m=\u001b[39m graphviz_layout(G, prog\u001b[39m=\u001b[39;49m\u001b[39m\"\u001b[39;49m\u001b[39mdot\u001b[39;49m\u001b[39m\"\u001b[39;49m)\n\u001b[0;32m    187\u001b[0m fig\u001b[39m=\u001b[39mplt\u001b[39m.\u001b[39mfigure(figsize\u001b[39m=\u001b[39m(\u001b[39m14\u001b[39m, \u001b[39m10\u001b[39m))\n\u001b[0;32m    188\u001b[0m ax\u001b[39m=\u001b[39mplt\u001b[39m.\u001b[39msubplot(\u001b[39m111\u001b[39m)\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\networkx\\drawing\\nx_pydot.py:359\u001b[0m, in \u001b[0;36mgraphviz_layout\u001b[1;34m(G, prog, root)\u001b[0m\n\u001b[0;32m    351\u001b[0m msg \u001b[39m=\u001b[39m (\n\u001b[0;32m    352\u001b[0m     \u001b[39m\"\u001b[39m\u001b[39mnx.nx_pydot.graphviz_layout depends on the pydot package, which has \u001b[39m\u001b[39m\"\u001b[39m\n\u001b[0;32m    353\u001b[0m     \u001b[39m\"\u001b[39m\u001b[39mknown issues and is not actively maintained. Consider using \u001b[39m\u001b[39m\"\u001b[39m\n\u001b[0;32m    354\u001b[0m     \u001b[39m\"\u001b[39m\u001b[39mnx.nx_agraph.graphviz_layout instead.\u001b[39m\u001b[39m\\n\u001b[39;00m\u001b[39m\\n\u001b[39;00m\u001b[39m\"\u001b[39m\n\u001b[0;32m    355\u001b[0m     \u001b[39m\"\u001b[39m\u001b[39mSee https://github.com/networkx/networkx/issues/5723\u001b[39m\u001b[39m\"\u001b[39m\n\u001b[0;32m    356\u001b[0m )\n\u001b[0;32m    357\u001b[0m warnings\u001b[39m.\u001b[39mwarn(msg, \u001b[39mDeprecationWarning\u001b[39;00m, stacklevel\u001b[39m=\u001b[39m\u001b[39m2\u001b[39m)\n\u001b[1;32m--> 359\u001b[0m \u001b[39mreturn\u001b[39;00m pydot_layout(G\u001b[39m=\u001b[39;49mG, prog\u001b[39m=\u001b[39;49mprog, root\u001b[39m=\u001b[39;49mroot)\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\networkx\\drawing\\nx_pydot.py:414\u001b[0m, in \u001b[0;36mpydot_layout\u001b[1;34m(G, prog, root)\u001b[0m\n\u001b[0;32m    410\u001b[0m     P\u001b[39m.\u001b[39mset(\u001b[39m\"\u001b[39m\u001b[39mroot\u001b[39m\u001b[39m\"\u001b[39m, \u001b[39mstr\u001b[39m(root))\n\u001b[0;32m    412\u001b[0m \u001b[39m# List of low-level bytes comprising a string in the dot language converted\u001b[39;00m\n\u001b[0;32m    413\u001b[0m \u001b[39m# from the passed graph with the passed external GraphViz command.\u001b[39;00m\n\u001b[1;32m--> 414\u001b[0m D_bytes \u001b[39m=\u001b[39m P\u001b[39m.\u001b[39;49mcreate_dot(prog\u001b[39m=\u001b[39;49mprog)\n\u001b[0;32m    416\u001b[0m \u001b[39m# Unique string decoded from these bytes with the preferred locale encoding\u001b[39;00m\n\u001b[0;32m    417\u001b[0m D \u001b[39m=\u001b[39m \u001b[39mstr\u001b[39m(D_bytes, encoding\u001b[39m=\u001b[39mgetpreferredencoding())\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\pydot.py:1733\u001b[0m, in \u001b[0;36mDot.__init__.<locals>.new_method\u001b[1;34m(f, prog, encoding)\u001b[0m\n\u001b[0;32m   1729\u001b[0m \u001b[39mdef\u001b[39;00m \u001b[39mnew_method\u001b[39m(\n\u001b[0;32m   1730\u001b[0m         f\u001b[39m=\u001b[39mfrmt, prog\u001b[39m=\u001b[39m\u001b[39mself\u001b[39m\u001b[39m.\u001b[39mprog,\n\u001b[0;32m   1731\u001b[0m         encoding\u001b[39m=\u001b[39m\u001b[39mNone\u001b[39;00m):\n\u001b[0;32m   1732\u001b[0m \u001b[39m    \u001b[39m\u001b[39m\"\"\"Refer to docstring of method `create`.\"\"\"\u001b[39;00m\n\u001b[1;32m-> 1733\u001b[0m     \u001b[39mreturn\u001b[39;00m \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49mcreate(\n\u001b[0;32m   1734\u001b[0m         \u001b[39mformat\u001b[39;49m\u001b[39m=\u001b[39;49mf, prog\u001b[39m=\u001b[39;49mprog, encoding\u001b[39m=\u001b[39;49mencoding)\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\pydot.py:1933\u001b[0m, in \u001b[0;36mDot.create\u001b[1;34m(self, prog, format, encoding)\u001b[0m\n\u001b[0;32m   1930\u001b[0m     args \u001b[39m=\u001b[39m \u001b[39mlist\u001b[39m(e\u001b[39m.\u001b[39margs)\n\u001b[0;32m   1931\u001b[0m     args[\u001b[39m1\u001b[39m] \u001b[39m=\u001b[39m \u001b[39m'\u001b[39m\u001b[39m\"\u001b[39m\u001b[39m{prog}\u001b[39;00m\u001b[39m\"\u001b[39m\u001b[39m not found in path.\u001b[39m\u001b[39m'\u001b[39m\u001b[39m.\u001b[39mformat(\n\u001b[0;32m   1932\u001b[0m         prog\u001b[39m=\u001b[39mprog)\n\u001b[1;32m-> 1933\u001b[0m     \u001b[39mraise\u001b[39;00m \u001b[39mOSError\u001b[39;00m(\u001b[39m*\u001b[39margs)\n\u001b[0;32m   1934\u001b[0m \u001b[39melse\u001b[39;00m:\n\u001b[0;32m   1935\u001b[0m     \u001b[39mraise\u001b[39;00m\n",
      "\u001b[1;31mFileNotFoundError\u001b[0m: [WinError 2] \"dot\" not found in path."
     ]
    }
   ],
   "source": [
    "tree = []\n",
    "build_tree_recursive(X_train, y_train, [0,1,2,3,4,5,6,7,8,9], \"Root\", max_depth=1, current_depth=0, tree = tree)\n",
    "\n",
    "generate_tree_viz([0,1,2,3,4,5,6,7,8,9], y_train, tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The process is **recursive**, which means we must perform these calculations for each node until we meet a stopping criteria:\n",
    "\n",
    "- If the tree depth after splitting exceeds a threshold\n",
    "- If the resulting node has only 1 class\n",
    "- If the information gain of splitting is below a threshold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The final tree looks like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Depth 0, Root: Split on feature: 0\n",
      "- Depth 1, Left: Split on feature: 1\n",
      "  -- Left leaf node with indices [0, 4, 5, 7]\n",
      "  -- Right leaf node with indices [3]\n",
      "- Depth 1, Right: Split on feature: 2\n",
      "  -- Left leaf node with indices [1]\n",
      "  -- Right leaf node with indices [2, 6, 8, 9]\n"
     ]
    },
    {
     "ename": "FileNotFoundError",
     "evalue": "[WinError 2] \"dot\" not found in path.",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mFileNotFoundError\u001b[0m                         Traceback (most recent call last)",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\pydot.py:1923\u001b[0m, in \u001b[0;36mDot.create\u001b[1;34m(self, prog, format, encoding)\u001b[0m\n\u001b[0;32m   1922\u001b[0m \u001b[39mtry\u001b[39;00m:\n\u001b[1;32m-> 1923\u001b[0m     stdout_data, stderr_data, process \u001b[39m=\u001b[39m call_graphviz(\n\u001b[0;32m   1924\u001b[0m         program\u001b[39m=\u001b[39;49mprog,\n\u001b[0;32m   1925\u001b[0m         arguments\u001b[39m=\u001b[39;49marguments,\n\u001b[0;32m   1926\u001b[0m         working_dir\u001b[39m=\u001b[39;49mtmp_dir,\n\u001b[0;32m   1927\u001b[0m     )\n\u001b[0;32m   1928\u001b[0m \u001b[39mexcept\u001b[39;00m \u001b[39mOSError\u001b[39;00m \u001b[39mas\u001b[39;00m e:\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\pydot.py:132\u001b[0m, in \u001b[0;36mcall_graphviz\u001b[1;34m(program, arguments, working_dir, **kwargs)\u001b[0m\n\u001b[0;32m    130\u001b[0m program_with_args \u001b[39m=\u001b[39m [program, ] \u001b[39m+\u001b[39m arguments\n\u001b[1;32m--> 132\u001b[0m process \u001b[39m=\u001b[39m subprocess\u001b[39m.\u001b[39mPopen(\n\u001b[0;32m    133\u001b[0m     program_with_args,\n\u001b[0;32m    134\u001b[0m     env\u001b[39m=\u001b[39menv,\n\u001b[0;32m    135\u001b[0m     cwd\u001b[39m=\u001b[39mworking_dir,\n\u001b[0;32m    136\u001b[0m     shell\u001b[39m=\u001b[39m\u001b[39mFalse\u001b[39;00m,\n\u001b[0;32m    137\u001b[0m     stderr\u001b[39m=\u001b[39msubprocess\u001b[39m.\u001b[39mPIPE,\n\u001b[0;32m    138\u001b[0m     stdout\u001b[39m=\u001b[39msubprocess\u001b[39m.\u001b[39mPIPE,\n\u001b[0;32m    139\u001b[0m     \u001b[39m*\u001b[39m\u001b[39m*\u001b[39mkwargs\n\u001b[0;32m    140\u001b[0m )\n\u001b[0;32m    141\u001b[0m stdout_data, stderr_data \u001b[39m=\u001b[39m process\u001b[39m.\u001b[39mcommunicate()\n",
      "File \u001b[1;32m~\\AppData\\Local\\Programs\\Python\\Python310\\lib\\subprocess.py:971\u001b[0m, in \u001b[0;36mPopen.__init__\u001b[1;34m(self, args, bufsize, executable, stdin, stdout, stderr, preexec_fn, close_fds, shell, cwd, env, universal_newlines, startupinfo, creationflags, restore_signals, start_new_session, pass_fds, user, group, extra_groups, encoding, errors, text, umask, pipesize)\u001b[0m\n\u001b[0;32m    968\u001b[0m             \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mstderr \u001b[39m=\u001b[39m io\u001b[39m.\u001b[39mTextIOWrapper(\u001b[39mself\u001b[39m\u001b[39m.\u001b[39mstderr,\n\u001b[0;32m    969\u001b[0m                     encoding\u001b[39m=\u001b[39mencoding, errors\u001b[39m=\u001b[39merrors)\n\u001b[1;32m--> 971\u001b[0m     \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49m_execute_child(args, executable, preexec_fn, close_fds,\n\u001b[0;32m    972\u001b[0m                         pass_fds, cwd, env,\n\u001b[0;32m    973\u001b[0m                         startupinfo, creationflags, shell,\n\u001b[0;32m    974\u001b[0m                         p2cread, p2cwrite,\n\u001b[0;32m    975\u001b[0m                         c2pread, c2pwrite,\n\u001b[0;32m    976\u001b[0m                         errread, errwrite,\n\u001b[0;32m    977\u001b[0m                         restore_signals,\n\u001b[0;32m    978\u001b[0m                         gid, gids, uid, umask,\n\u001b[0;32m    979\u001b[0m                         start_new_session)\n\u001b[0;32m    980\u001b[0m \u001b[39mexcept\u001b[39;00m:\n\u001b[0;32m    981\u001b[0m     \u001b[39m# Cleanup if the child failed starting.\u001b[39;00m\n",
      "File \u001b[1;32m~\\AppData\\Local\\Programs\\Python\\Python310\\lib\\subprocess.py:1440\u001b[0m, in \u001b[0;36mPopen._execute_child\u001b[1;34m(self, args, executable, preexec_fn, close_fds, pass_fds, cwd, env, startupinfo, creationflags, shell, p2cread, p2cwrite, c2pread, c2pwrite, errread, errwrite, unused_restore_signals, unused_gid, unused_gids, unused_uid, unused_umask, unused_start_new_session)\u001b[0m\n\u001b[0;32m   1439\u001b[0m \u001b[39mtry\u001b[39;00m:\n\u001b[1;32m-> 1440\u001b[0m     hp, ht, pid, tid \u001b[39m=\u001b[39m _winapi\u001b[39m.\u001b[39;49mCreateProcess(executable, args,\n\u001b[0;32m   1441\u001b[0m                              \u001b[39m# no special security\u001b[39;49;00m\n\u001b[0;32m   1442\u001b[0m                              \u001b[39mNone\u001b[39;49;00m, \u001b[39mNone\u001b[39;49;00m,\n\u001b[0;32m   1443\u001b[0m                              \u001b[39mint\u001b[39;49m(\u001b[39mnot\u001b[39;49;00m close_fds),\n\u001b[0;32m   1444\u001b[0m                              creationflags,\n\u001b[0;32m   1445\u001b[0m                              env,\n\u001b[0;32m   1446\u001b[0m                              cwd,\n\u001b[0;32m   1447\u001b[0m                              startupinfo)\n\u001b[0;32m   1448\u001b[0m \u001b[39mfinally\u001b[39;00m:\n\u001b[0;32m   1449\u001b[0m     \u001b[39m# Child is launched. Close the parent's copy of those pipe\u001b[39;00m\n\u001b[0;32m   1450\u001b[0m     \u001b[39m# handles that only the child should have open.  You need\u001b[39;00m\n\u001b[1;32m   (...)\u001b[0m\n\u001b[0;32m   1453\u001b[0m     \u001b[39m# pipe will not close when the child process exits and the\u001b[39;00m\n\u001b[0;32m   1454\u001b[0m     \u001b[39m# ReadFile will hang.\u001b[39;00m\n",
      "\u001b[1;31mFileNotFoundError\u001b[0m: [WinError 2] The system cannot find the file specified",
      "\nDuring handling of the above exception, another exception occurred:\n",
      "\u001b[1;31mFileNotFoundError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\C2 - Advanced Learning Algorithms\\week4\\optional labs\\C2_W4_Lab_01_Decision_Trees.ipynb Cell 29\u001b[0m line \u001b[0;36m3\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/TA/machine-learning-specialization-coursera/C2%20-%20Advanced%20Learning%20Algorithms/week4/optional%20labs/C2_W4_Lab_01_Decision_Trees.ipynb#X42sZmlsZQ%3D%3D?line=0'>1</a>\u001b[0m tree \u001b[39m=\u001b[39m []\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/TA/machine-learning-specialization-coursera/C2%20-%20Advanced%20Learning%20Algorithms/week4/optional%20labs/C2_W4_Lab_01_Decision_Trees.ipynb#X42sZmlsZQ%3D%3D?line=1'>2</a>\u001b[0m build_tree_recursive(X_train, y_train, [\u001b[39m0\u001b[39m,\u001b[39m1\u001b[39m,\u001b[39m2\u001b[39m,\u001b[39m3\u001b[39m,\u001b[39m4\u001b[39m,\u001b[39m5\u001b[39m,\u001b[39m6\u001b[39m,\u001b[39m7\u001b[39m,\u001b[39m8\u001b[39m,\u001b[39m9\u001b[39m], \u001b[39m\"\u001b[39m\u001b[39mRoot\u001b[39m\u001b[39m\"\u001b[39m, max_depth\u001b[39m=\u001b[39m\u001b[39m2\u001b[39m, current_depth\u001b[39m=\u001b[39m\u001b[39m0\u001b[39m, tree \u001b[39m=\u001b[39m tree)\n\u001b[1;32m----> <a href='vscode-notebook-cell:/d%3A/TA/machine-learning-specialization-coursera/C2%20-%20Advanced%20Learning%20Algorithms/week4/optional%20labs/C2_W4_Lab_01_Decision_Trees.ipynb#X42sZmlsZQ%3D%3D?line=2'>3</a>\u001b[0m generate_tree_viz([\u001b[39m0\u001b[39;49m,\u001b[39m1\u001b[39;49m,\u001b[39m2\u001b[39;49m,\u001b[39m3\u001b[39;49m,\u001b[39m4\u001b[39;49m,\u001b[39m5\u001b[39;49m,\u001b[39m6\u001b[39;49m,\u001b[39m7\u001b[39;49m,\u001b[39m8\u001b[39;49m,\u001b[39m9\u001b[39;49m], y_train, tree)\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\C2 - Advanced Learning Algorithms\\week4\\optional labs\\utils.py:185\u001b[0m, in \u001b[0;36mgenerate_tree_viz\u001b[1;34m(root_indices, y, tree)\u001b[0m\n\u001b[0;32m    181\u001b[0m     root \u001b[39m+\u001b[39m\u001b[39m=\u001b[39m \u001b[39m1\u001b[39m\n\u001b[0;32m    184\u001b[0m node_names \u001b[39m=\u001b[39m decision_names \u001b[39m+\u001b[39m leaf_names\n\u001b[1;32m--> 185\u001b[0m pos \u001b[39m=\u001b[39m graphviz_layout(G, prog\u001b[39m=\u001b[39;49m\u001b[39m\"\u001b[39;49m\u001b[39mdot\u001b[39;49m\u001b[39m\"\u001b[39;49m)\n\u001b[0;32m    187\u001b[0m fig\u001b[39m=\u001b[39mplt\u001b[39m.\u001b[39mfigure(figsize\u001b[39m=\u001b[39m(\u001b[39m14\u001b[39m, \u001b[39m10\u001b[39m))\n\u001b[0;32m    188\u001b[0m ax\u001b[39m=\u001b[39mplt\u001b[39m.\u001b[39msubplot(\u001b[39m111\u001b[39m)\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\networkx\\drawing\\nx_pydot.py:359\u001b[0m, in \u001b[0;36mgraphviz_layout\u001b[1;34m(G, prog, root)\u001b[0m\n\u001b[0;32m    351\u001b[0m msg \u001b[39m=\u001b[39m (\n\u001b[0;32m    352\u001b[0m     \u001b[39m\"\u001b[39m\u001b[39mnx.nx_pydot.graphviz_layout depends on the pydot package, which has \u001b[39m\u001b[39m\"\u001b[39m\n\u001b[0;32m    353\u001b[0m     \u001b[39m\"\u001b[39m\u001b[39mknown issues and is not actively maintained. Consider using \u001b[39m\u001b[39m\"\u001b[39m\n\u001b[0;32m    354\u001b[0m     \u001b[39m\"\u001b[39m\u001b[39mnx.nx_agraph.graphviz_layout instead.\u001b[39m\u001b[39m\\n\u001b[39;00m\u001b[39m\\n\u001b[39;00m\u001b[39m\"\u001b[39m\n\u001b[0;32m    355\u001b[0m     \u001b[39m\"\u001b[39m\u001b[39mSee https://github.com/networkx/networkx/issues/5723\u001b[39m\u001b[39m\"\u001b[39m\n\u001b[0;32m    356\u001b[0m )\n\u001b[0;32m    357\u001b[0m warnings\u001b[39m.\u001b[39mwarn(msg, \u001b[39mDeprecationWarning\u001b[39;00m, stacklevel\u001b[39m=\u001b[39m\u001b[39m2\u001b[39m)\n\u001b[1;32m--> 359\u001b[0m \u001b[39mreturn\u001b[39;00m pydot_layout(G\u001b[39m=\u001b[39;49mG, prog\u001b[39m=\u001b[39;49mprog, root\u001b[39m=\u001b[39;49mroot)\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\networkx\\drawing\\nx_pydot.py:414\u001b[0m, in \u001b[0;36mpydot_layout\u001b[1;34m(G, prog, root)\u001b[0m\n\u001b[0;32m    410\u001b[0m     P\u001b[39m.\u001b[39mset(\u001b[39m\"\u001b[39m\u001b[39mroot\u001b[39m\u001b[39m\"\u001b[39m, \u001b[39mstr\u001b[39m(root))\n\u001b[0;32m    412\u001b[0m \u001b[39m# List of low-level bytes comprising a string in the dot language converted\u001b[39;00m\n\u001b[0;32m    413\u001b[0m \u001b[39m# from the passed graph with the passed external GraphViz command.\u001b[39;00m\n\u001b[1;32m--> 414\u001b[0m D_bytes \u001b[39m=\u001b[39m P\u001b[39m.\u001b[39;49mcreate_dot(prog\u001b[39m=\u001b[39;49mprog)\n\u001b[0;32m    416\u001b[0m \u001b[39m# Unique string decoded from these bytes with the preferred locale encoding\u001b[39;00m\n\u001b[0;32m    417\u001b[0m D \u001b[39m=\u001b[39m \u001b[39mstr\u001b[39m(D_bytes, encoding\u001b[39m=\u001b[39mgetpreferredencoding())\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\pydot.py:1733\u001b[0m, in \u001b[0;36mDot.__init__.<locals>.new_method\u001b[1;34m(f, prog, encoding)\u001b[0m\n\u001b[0;32m   1729\u001b[0m \u001b[39mdef\u001b[39;00m \u001b[39mnew_method\u001b[39m(\n\u001b[0;32m   1730\u001b[0m         f\u001b[39m=\u001b[39mfrmt, prog\u001b[39m=\u001b[39m\u001b[39mself\u001b[39m\u001b[39m.\u001b[39mprog,\n\u001b[0;32m   1731\u001b[0m         encoding\u001b[39m=\u001b[39m\u001b[39mNone\u001b[39;00m):\n\u001b[0;32m   1732\u001b[0m \u001b[39m    \u001b[39m\u001b[39m\"\"\"Refer to docstring of method `create`.\"\"\"\u001b[39;00m\n\u001b[1;32m-> 1733\u001b[0m     \u001b[39mreturn\u001b[39;00m \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49mcreate(\n\u001b[0;32m   1734\u001b[0m         \u001b[39mformat\u001b[39;49m\u001b[39m=\u001b[39;49mf, prog\u001b[39m=\u001b[39;49mprog, encoding\u001b[39m=\u001b[39;49mencoding)\n",
      "File \u001b[1;32md:\\TA\\machine-learning-specialization-coursera\\.venv\\lib\\site-packages\\pydot.py:1933\u001b[0m, in \u001b[0;36mDot.create\u001b[1;34m(self, prog, format, encoding)\u001b[0m\n\u001b[0;32m   1930\u001b[0m     args \u001b[39m=\u001b[39m \u001b[39mlist\u001b[39m(e\u001b[39m.\u001b[39margs)\n\u001b[0;32m   1931\u001b[0m     args[\u001b[39m1\u001b[39m] \u001b[39m=\u001b[39m \u001b[39m'\u001b[39m\u001b[39m\"\u001b[39m\u001b[39m{prog}\u001b[39;00m\u001b[39m\"\u001b[39m\u001b[39m not found in path.\u001b[39m\u001b[39m'\u001b[39m\u001b[39m.\u001b[39mformat(\n\u001b[0;32m   1932\u001b[0m         prog\u001b[39m=\u001b[39mprog)\n\u001b[1;32m-> 1933\u001b[0m     \u001b[39mraise\u001b[39;00m \u001b[39mOSError\u001b[39;00m(\u001b[39m*\u001b[39margs)\n\u001b[0;32m   1934\u001b[0m \u001b[39melse\u001b[39;00m:\n\u001b[0;32m   1935\u001b[0m     \u001b[39mraise\u001b[39;00m\n",
      "\u001b[1;31mFileNotFoundError\u001b[0m: [WinError 2] \"dot\" not found in path."
     ]
    }
   ],
   "source": [
    "tree = []\n",
    "build_tree_recursive(X_train, y_train, [0,1,2,3,4,5,6,7,8,9], \"Root\", max_depth=2, current_depth=0, tree = tree)\n",
    "generate_tree_viz([0,1,2,3,4,5,6,7,8,9], y_train, tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Congratulations! You completed the notebook!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.10"
  },
  "vscode": {
   "interpreter": {
    "hash": "56d44d6a8424451b5ce45d1ae0b0b7865dc60710e7f74571dd51dd80d7829ee9"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
